{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "堆\n",
    "\n",
    "    父节点的键值总是大于或等于（小于或等于）任何一个子节点的键值。\n",
    "    \n",
    "    \n",
    "    一般都用数组来表示堆，i结点的父结点下标就为(i – 1) / 2。它的左右子结点下标分别为2 * i +\n",
    "    1和2 * i + 2。如第0个结点左右子结点下标分别为1和2。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "堆排序："
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "    1、构造最大堆（Build_Max_Heap）：若数组下标范围为0~n，考虑到单独一个元素是大根堆，则从下标n/2开始的元素均为大根堆。于是只要从n/2-1开始，向前依次构造大根堆，这样就能保证，构造到某个节点时，它的左右子树都已经是大根堆。\n",
    "\n",
    "    2、堆排序（HeapSort）：由于堆是用数组模拟的。得到一个大根堆后，数组内部并不是有序的。因此需要将堆化数组有序化。思想是移除根节点，并做最大堆调整的递归运算。第一次将heap[0]与heap[n-1]交换，再对heap[0…n-2]做最大堆调整。第二次将heap[0]与heap[n-2]交换，再对heap[0…n-3]做最大堆调整。重复该操作直至heap[0]和heap[1]交换。由于每次都是将最大的数并入到后面的有序区间，故操作完后整个数组就是有序的了。\n",
    "    \n",
    "    ## 堆排序就是把堆顶的最大数取出, \n",
    "    ## 将剩余的堆继续调整为最大堆,具体过程在第二块有介绍,以递归实现 \n",
    "    ## 剩余部分调整为最大堆后,再次将堆顶的最大数取出,再将剩余部分调整为最大堆,这个过程持续到剩余数只有一个时结束\n",
    "\n",
    "    3、最大堆调整（Max_Heapify）：该方法是提供给上述两个过程调用的。目的是将堆的末端子节点作调整，使得子节点永远小于父节点 。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 69,
   "metadata": {},
   "outputs": [],
   "source": [
    "def heap_sort(nums):\n",
    "    n = len(nums)\n",
    "    first = n // 2 -1  # 最后一个非叶子节点\n",
    "    print('first',first)\n",
    "    for i in range(first, -1, -1):    # 从最后一个有子节点的孩子调整最大堆\n",
    "        max_heapify(nums, i, n-1)\n",
    "        print(nums)\n",
    "    print('=================================== 第一次的最大堆建好了,根节点一定是最大值，为啥呢？')\n",
    "    print(\"=================================== 因为我们每一次比较都是在父节点和两个子节点间进行的\")\n",
    "    print(\"=================================== 然后把三个中间最大的值，放在父亲节点中\")\n",
    "    print(\"=================================== 一层一层往上做同样的动作，这样就把最大的值拱到根节点了。\")\n",
    "    for j in range(n-1, 0, -1):      # 将最大的放到堆的最后一个, 堆-1, 继续调整排序\n",
    "        nums[j], nums[0] = nums[0], nums[j]  #将根节点元素与最后叶子节点进行互换，取出最大根节点元素，对剩余节点重新构建最大堆\n",
    "        max_heapify(nums, 0, j-1)     #因为end上面取的是n-1，故而这里直接放end-1，相当于忽略了最后最大根节点元素ary[n-1]\n",
    "    return nums\n",
    "\n",
    "def max_heapify(nums, start, end):\n",
    "    #start为当前需要调整最大堆的位置，end为调整边界\n",
    "    root = start\n",
    "    print('nums[root]',nums[root])\n",
    "    while True:\n",
    "        child = root * 2 + 1  # 调整节点的子节点\n",
    "        print('child',child)\n",
    "        if child > end:\n",
    "            print('## break child > end')\n",
    "            break\n",
    "        print('nums[child]',nums[child])\n",
    "        if child + 1 <= end and nums[child] < nums[child +1]:\n",
    "            child = child + 1        # 取较大的子节点\n",
    "        if nums[root] < nums[child]: # 较大的子节点成为父节点\n",
    "            nums[root], nums[child] = nums[child], nums[root]\n",
    "            root = child\n",
    "        else:\n",
    "            break\n",
    "        print('nums',nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 70,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "nums = [1,4,8,3,7,2,15,9,16]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 71,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "first 3\n",
      "nums[root] 3\n",
      "child 7\n",
      "nums[child] 9\n",
      "nums [1, 4, 8, 16, 7, 2, 15, 9, 3]\n",
      "child 17\n",
      "## break child > end\n",
      "[1, 4, 8, 16, 7, 2, 15, 9, 3]\n",
      "nums[root] 8\n",
      "child 5\n",
      "nums[child] 2\n",
      "nums [1, 4, 15, 16, 7, 2, 8, 9, 3]\n",
      "child 13\n",
      "## break child > end\n",
      "[1, 4, 15, 16, 7, 2, 8, 9, 3]\n",
      "nums[root] 4\n",
      "child 3\n",
      "nums[child] 16\n",
      "nums [1, 16, 15, 4, 7, 2, 8, 9, 3]\n",
      "child 7\n",
      "nums[child] 9\n",
      "nums [1, 16, 15, 9, 7, 2, 8, 4, 3]\n",
      "child 15\n",
      "## break child > end\n",
      "[1, 16, 15, 9, 7, 2, 8, 4, 3]\n",
      "nums[root] 1\n",
      "child 1\n",
      "nums[child] 16\n",
      "nums [16, 1, 15, 9, 7, 2, 8, 4, 3]\n",
      "child 3\n",
      "nums[child] 9\n",
      "nums [16, 9, 15, 1, 7, 2, 8, 4, 3]\n",
      "child 7\n",
      "nums[child] 4\n",
      "nums [16, 9, 15, 4, 7, 2, 8, 1, 3]\n",
      "child 15\n",
      "## break child > end\n",
      "[16, 9, 15, 4, 7, 2, 8, 1, 3]\n",
      "=================================== 第一次的最大堆建好了\n",
      "nums[root] 3\n",
      "child 1\n",
      "nums[child] 9\n",
      "nums [15, 9, 3, 4, 7, 2, 8, 1, 16]\n",
      "child 5\n",
      "nums[child] 2\n",
      "nums [15, 9, 8, 4, 7, 2, 3, 1, 16]\n",
      "child 13\n",
      "## break child > end\n",
      "nums[root] 1\n",
      "child 1\n",
      "nums[child] 9\n",
      "nums [9, 1, 8, 4, 7, 2, 3, 15, 16]\n",
      "child 3\n",
      "nums[child] 4\n",
      "nums [9, 7, 8, 4, 1, 2, 3, 15, 16]\n",
      "child 9\n",
      "## break child > end\n",
      "nums[root] 3\n",
      "child 1\n",
      "nums[child] 7\n",
      "nums [8, 7, 3, 4, 1, 2, 9, 15, 16]\n",
      "child 5\n",
      "nums[child] 2\n",
      "nums[root] 2\n",
      "child 1\n",
      "nums[child] 7\n",
      "nums [7, 2, 3, 4, 1, 8, 9, 15, 16]\n",
      "child 3\n",
      "nums[child] 4\n",
      "nums [7, 4, 3, 2, 1, 8, 9, 15, 16]\n",
      "child 7\n",
      "## break child > end\n",
      "nums[root] 1\n",
      "child 1\n",
      "nums[child] 4\n",
      "nums [4, 1, 3, 2, 7, 8, 9, 15, 16]\n",
      "child 3\n",
      "nums[child] 2\n",
      "nums [4, 2, 3, 1, 7, 8, 9, 15, 16]\n",
      "child 7\n",
      "## break child > end\n",
      "nums[root] 1\n",
      "child 1\n",
      "nums[child] 2\n",
      "nums [3, 2, 1, 4, 7, 8, 9, 15, 16]\n",
      "child 5\n",
      "## break child > end\n",
      "nums[root] 1\n",
      "child 1\n",
      "nums[child] 2\n",
      "nums [2, 1, 3, 4, 7, 8, 9, 15, 16]\n",
      "child 3\n",
      "## break child > end\n",
      "nums[root] 1\n",
      "child 1\n",
      "## break child > end\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "[1, 2, 3, 4, 7, 8, 9, 15, 16]"
      ]
     },
     "execution_count": 71,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "heap_sort(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "10\n",
      "9\n",
      "8\n",
      "7\n",
      "6\n",
      "5\n",
      "4\n"
     ]
    }
   ],
   "source": [
    "for i in range(10, 3, -1):\n",
    "    print(i)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
